// Magic Software, Inc.
// http://www.magic-software.com
// Copyright (c) 2000, All Rights Reserved
//
// Source code from Magic Software is supplied under the terms of a license
// agreement and may not be copied or disclosed except in accordance with the
// terms of that agreement.  The various license agreements may be found at
// the Magic Software web site.  This file is subject to the license
//
// FREE SOURCE CODE
// http://www.magic-software.com/License/free.pdf

#ifndef MGCPOLYNOMIAL_H
#define MGCPOLYNOMIAL_H

#include "MgcMath.h"


class MgcPolynomial
{
public:
    // construction and destruction
    MgcPolynomial (int iDegree = -1);
    MgcPolynomial (const MgcPolynomial& rkPoly);
    ~MgcPolynomial ();

    // assignment
    MgcPolynomial& operator= (const MgcPolynomial& rkPoly);

    // coefficient access
    void SetDegree (int iDegree);
    int GetDegree () const;
    MgcReal& operator[] (int i) const;

    // evaluation
    MgcReal operator() (MgcReal fT) const;

    // derivation
    MgcPolynomial GetDerivative () const;

    // inversion ( invpoly[i] = poly[degree-i] for 0 <= i <= degree )
    MgcPolynomial GetInversion () const;

    // arithmetic
    MgcPolynomial operator+ (const MgcPolynomial& rkPoly) const;
    MgcPolynomial operator- (const MgcPolynomial& rkPoly) const;
    MgcPolynomial operator* (const MgcPolynomial& rkPoly) const;
    MgcPolynomial operator* (MgcReal fScalar) const;
    MgcPolynomial operator- () const;
    friend MgcPolynomial operator* (MgcReal fScalar,
        const MgcPolynomial& rkPoly);

    // root finding
    static int DIGITS_ACCURACY;
    static MgcReal ZERO_TOLERANCE;
    bool Bisection (MgcReal fXMin, MgcReal fXMax, MgcReal& rfRoot) const;
    void GetRootsOnInterval (MgcReal fXMin, MgcReal fXMax,
        int& riCount, MgcReal* afRoot) const;
    void GetAllRoots (int& riCount, MgcReal* afRoot) const;

    MgcReal GetRootBound () const;  // real roots must be in [-bound,bound]
    bool AllRealPartsNegative () const;
    bool AllRealPartsPositive () const;

    // low-degree root finding (degree must be correct, must be monic poly)
    bool RootsDegree2 (int& riCount, MgcReal afRoot[2]) const;
    bool RootsDegree3 (int& riCount, MgcReal afRoot[3]) const;
    bool RootsDegree4 (int& riCount, MgcReal afRoot[4]) const;

    // solve A*r^3 + B*r = C where A > 0 and B > 0
    MgcReal SpecialCubeRoot (MgcReal fA, MgcReal fB, MgcReal fC);

protected:
    int m_iDegree;
    MgcReal* m_afCoeff;

    // root finding
    static const MgcReal ms_fInvLog2;
    static const MgcReal ms_fLog10;
    static const MgcReal ms_fThird;
    static const MgcReal ms_fSqrt3;
    static const MgcReal ms_fTwentySeventh;
    static bool AllRealPartsNegative (int iDegree, MgcReal* afCoeff);

    // TO DO.  Sturm sequences for counting roots on interval.
};

#endif
